package com.sunny.l72;
/**
 *  Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

 For example,
 If n = 4 and k = 2, a solution is:

 [
 [2,4],
 [3,4],
 [2,3],
 [1,2],
 [1,3],
 [1,4],
 ]


 */

import java.util.ArrayList;

/**
 * @Author zsunny
 * @Date 2018/9/22 20:39
 * @Mail zsunny@yeah.net
 */
public class Solution {

    public static void main(String[] args) {

        Solution solution = new Solution();
        System.out.println(solution.combine(4, 2));

    }

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        if(n < k){
            return res;
        }
        ArrayList<Integer> list = new ArrayList<>();
        dfs(n, k, list, 1);
        return res;
    }
    public void dfs(int n, int k, ArrayList<Integer> list, int ind){
        if(n-ind+1+list.size() < k)
            return;
        if(ind > n){
            if(list.size() == k){
                res.add(list);
            }else{
                return;
            }
        }
        ArrayList<Integer> list1 = new ArrayList<>(list);
        dfs(n, k, list1, ind+1);
        ArrayList<Integer> list2 = new ArrayList<>(list);
        list2.add(ind);
        dfs(n, k, list2, ind+1);
    }
}
